Date: Wednesday, 15-Jan-97 00:23:28 GMT
Server: NCSA/1.3
MIME-version: 1.0
Content-type: text/html
Last-modified: Monday, 11-Nov-96 01:51:25 GMT
Content-length: 13878

<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
<HTML>
<HEAD>
<TITLE>No Title</TITLE>
<META NAME="description" CONTENT="No Title">
<META NAME="keywords" CONTENT="resume-book-journal">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<LINK REL=STYLESHEET HREF="resume-book-journal.css">
</HEAD>
<BODY LANG="EN">
 <!WA0><A NAME="tex2html1" HREF="http://www.cs.rochester.edu/u/lane/node1.html"><!WA1><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.cs.rochester.edu/u/jag/icons/next_motif.gif"></A> <!WA2><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.cs.rochester.edu/u/jag/icons/up_motif_gr.gif"> <!WA3><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.rochester.edu/u/jag/icons/previous_motif_gr.gif">   <BR>
<B> Next:</B> <!WA4><A NAME="tex2html2" HREF="http://www.cs.rochester.edu/u/lane/node1.html">  About this document </A>
<BR> 
<P>
<H2><!WA5><A HREF="http://www.cs.rochester.edu/u/lane/home.html">Go back to Lane's home page</A></H2>
<P>
<EM>Most of the recent papers from this list can be found, in their
technical report versions, in the UR CS technical report on-line
archive, which can be reached via my home page.</EM>
<P>
<B>JOURNAL AND BOOK PUBLICATIONS (Last Updated: 11/96) <BR> 
Lane A. Hemaspaandra 
(born&nbsp;Lane 
A. Hemachandra) </B> 
<BR> <P>
<P>
<OL><B>BOOKS IN PREPARATION OR TO APPEAR</B>
<LI> <A NAME="binprepccc">&#160;</A>
<B>The Complexity Theory Companion</B>,
L.&nbsp;Hemaspaandra and M.&nbsp;Ogihara,
in preparation.<LI> <A NAME="binprepsfc">&#160;</A>
<B>Semi-Feasible Computation</B>,
L.&nbsp;Hemaspaandra and L.&nbsp;Torenvliet,
in preparation.<LI> <A NAME="binprepctrII">&#160;</A>
<B>Complexity Theory Retrospective II</B>,
L.&nbsp;Hemaspaandra and A.&nbsp;Selman, editors, Springer-Verlag,
to appear.
<P>
<P>
<P>
<P>
<P>
<B>BOOK CHAPTERS</B>
<P>
<LI>
<B>Witness-Isomorphic Reductions and Local Search</B>,
S.&nbsp;Fischer, L.&nbsp;Hemaspaandra, and L.&nbsp;Torenvliet, 
in&nbsp;Complexity, Logic and Recursion Theory,
ed.&nbsp;A.&nbsp;Sorbi, Marcel Dekker, Inc.,
to appear.<LI> 
<A NAME="hemdiscmathhandbook">&#160;</A>
<B>Complexity Classes</B>, L.&nbsp;Hemaspaandra,
section in&nbsp;Handbook of Discrete and Combinatorial Mathematics,
ed.&nbsp;K.&nbsp;Rosen,
CRC Press, to appear.<LI><A NAME="chvbook">&#160;</A>
<B>Promises and Fault-Tolerant Database Access</B>,
J.&nbsp;Cai, L.&nbsp;Hemachandra, and J.&nbsp;Vyskoc,
in&nbsp;Complexity Theory: Current Research,
eds. K.&nbsp;Ambos-Spies, S.&nbsp;Homer, and U.&nbsp;Sch&#246;ning,
Cambridge University Press, pp.&nbsp;101-146, 1993.<LI> <A NAME="tenauthorbookchapter">&#160;</A>
<B>Reductions to Sets of Low Information
Content</B>,
V.&nbsp;Arvind, Y.&nbsp;Han, L.&nbsp;Hemachandra, J.&nbsp;K&#246;bler,
A.&nbsp;Lozano, M.&nbsp;Mundhenk, M.&nbsp;Ogiwara, U.&nbsp;Sch&#246;ning,
R.&nbsp;Silvestri, and T.&nbsp;Thierauf, 
in&nbsp;Complexity Theory: Current Research,
eds. K.&nbsp;Ambos-Spies, S.&nbsp;Homer, and U.&nbsp;Sch&#246;ning,
Cambridge University Press, pp.&nbsp;1-45, 1993.<LI> <A NAME="hosubtractionbook">&#160;</A>
<B>Is #P Closed Under Subtraction?</B>,
L. Hemachandra and M. Ogiwara,
in&nbsp;Current Trends in Theoretical Computer Science:  Essays and 
Tutorials,
eds. G. Rozenberg and A. Salomaa,
World Scientific Press, pp.&nbsp;523-536, 1993.
<P>
<P>
<P>
<P>
<P>
<B>REFEREED JOURNAL PUBLICATIONS</B>
<P>
<LI>
<B>
Easy Sets and Hard Certificate Schemes</B>,
L.&nbsp;Hemaspaandra, J.&nbsp;Rothe, and G.&nbsp;Wechsung,
Acta Informatica,
accepted subject to minor revision.<LI> <B>
Logspace Reducibility:  Models
and Equivalences</B>, L.&nbsp;Hemaspaandra and Z.&nbsp;Jiang, 
International Journal of Foundations of Computer Science,
accepted subject to minor revision.<LI> <A NAME="jhemhemwecquery">&#160;</A>
<B>
Query Order</B>,
L.&nbsp;Hemaspaandra, H.&nbsp;Hempel, and G.&nbsp;Wechsung,
to appear in
SIAM Journal on Computing.<LI>  <A NAME="jourhanhemthibpp">&#160;</A>
<B>Threshold Computation and Cryptographic Security</B>,
Y.&nbsp;Han, L.&nbsp;Hemaspaandra, and T.&nbsp;Thierauf,
to appear in 
SIAM Journal on Computing.<LI>
<A NAME="jourhemrotupbh">&#160;</A>
<B>Unambiguous Computation:  Boolean Hierarchies and Sparse
Turing-Complete Sets</B>, L.&nbsp;Hemaspaandra and J.&nbsp;Rothe,
to appear in
SIAM Journal on Computing.<LI>
<A NAME="jourhanhemjourpseudo">&#160;</A>
<B>
Pseudorandom Generators and the Frequency of Simplicity</B>,
Y.&nbsp;Han and L.&nbsp;Hemaspaandra,
Journal of Cryptology,
V.&nbsp;9, #4, pp.&nbsp;251-262, Autumn 1996.<LI>
<A NAME="jouhemzim">&#160;</A>
<B>
Strong Self-Reducibility Precludes Strong Immunity</B>,
L.&nbsp;Hemaspaandra and M.&nbsp;Zimand,
Mathematical Systems Theory,
V.&nbsp;29, #5, pp.&nbsp;535-548,
September/October 1996.<LI> 
<A NAME="jourhemnaiogisel">&#160;</A>
<B>Computing Solutions Uniquely Collapses the Polynomial Hierarchy</B>,
L.&nbsp;Hemaspaandra, A.&nbsp;Naik, M.&nbsp;Ogihara, and A.&nbsp;Selman,
SIAM Journal on Computing, V.&nbsp;25, #4, pp.&nbsp;697-708, 
August 1996.<LI> <A NAME="jourhemhoeogipsel">&#160;</A>
<B>
Reducibility Classes of P-Selective Sets</B>,
L.&nbsp;Hemaspaandra, A.&nbsp;Hoene, and M.&nbsp;Ogihara,
Theoretical Computer Science, V.&nbsp;155, #2, pp.&nbsp;447-457,
March 1996.<LI>
<A NAME="themtorjouroptimaladvice">&#160;</A>
<B>
Optimal Advice</B>,
L.&nbsp;Hemaspaandra and L.&nbsp;Torenvliet, 
Theoretical Computer Science, V.&nbsp;154, #2, pp.&nbsp;367-377,
February 1996.<LI> <A NAME="jourhemhoeogiselthiwanicci">&#160;</A>
<B>Nondeterministically  Selective Sets</B>,
L.&nbsp;Hemaspaandra, A.&nbsp;Hoene, A.&nbsp;Naik, 
M.&nbsp;Ogihara, A.&nbsp;Selman, T.&nbsp;Thierauf, and 
J.&nbsp;Wang, 
International Journal of Foundations of Computer Science,
V.&nbsp;6, #4, pp.&nbsp;403-416, December 1995.<LI>
<A NAME="jourhemjhadefying">&#160;</A>
<B>Defying Upward and Downward Separation</B>,
L.&nbsp;Hemaspaandra and S.&nbsp;Jha,
Information and Computation, V.&nbsp;121, #1, pp.&nbsp;1-13, 
August 1995.<LI> <A NAME="jourhemsileasily">&#160;</A>
<B>Easily Checked Generalized Self-Reducibility</B>,
L.&nbsp;Hemaspaandra and R.&nbsp;Silvestri,
SIAM Journal on Computing, V.&nbsp;24, #4, pp.&nbsp;840-858, 
August
1995.<LI> <A NAME="jourhemjiapsel">&#160;</A>
<B>
P-Selectivity: Intersections and Indices</B>,
L.&nbsp;Hemaspaandra and Z.&nbsp;Jiang,
Theoretical Computer Science, V.&nbsp;145, #1-2, pp.&nbsp;371-380, 1995.
<P>
<LI><A NAME="jourhot">&#160;</A> 
<B>Space-Efficient Recognition
of Sparse Self-Reducible Languages</B>,
L.&nbsp;Hemaspaandra, M. Ogihara, and S. Toda,
Computational Complexity, V.&nbsp;4, #3, pp.&nbsp;262-296, 
1994.<LI> <A NAME="krahemmstgraph">&#160;</A>
<B>On the Complexity of Graph Reconstruction</B>, 
D.&nbsp;Kratsch and L.&nbsp;Hemaspaandra,
Mathematical Systems Theory, 
V.&nbsp;27, #3, pp.&nbsp;257-273, May/June 1994.<LI> <A NAME="hemspatcsquasi">&#160;</A>
<B>Quasi-Injective Reductions</B>,
E.&nbsp;Hemaspaandra and L.&nbsp;Hemaspaandra,
Theoretical Computer Science, V.&nbsp;123, #2, pp.&nbsp;407-413, 
January 1994.<LI> <A NAME="jourhjv">&#160;</A> 
<B>Banishing Robust Turing Completeness</B>,
L.&nbsp;Hemaspaandra, S.&nbsp;Jain, and N.&nbsp;Vereshchagin,
International Journal of Foundations of Computer Science, 
V.&nbsp;4, #3, pp.&nbsp;245-265, 1993.
<LI> <A NAME="gashemhoeinfcompterseness">&#160;</A>
<B>On Checking Versus Evaluation of Multiple 
Queries</B>, W. Gasarch, L.&nbsp;Hemachandra,
and A.&nbsp;Hoene, 
Information and Computation,
V.&nbsp;105, #1, pp.&nbsp;72-93, July 1993.<LI> 
<A NAME="hemogiclosure1">&#160;</A> <B>A Complexity Theory for Feasible Closure 
Properties</B>,
M. Ogiwara and L.&nbsp;Hemachandra,
Journal of Computer and System Sciences,
V.&nbsp;46, #3, pp.&nbsp;295-325, June 1993.<LI> <A NAME="hemhoejcss1">&#160;</A>
<B>Collapsing Degrees Via Strong Computation</B>, 
L.&nbsp;Hemachandra and A.&nbsp;Hoene,
Journal of Computer and System Sciences,
V.&nbsp;46, #3, pp.&nbsp;363-380, June 1993.<LI> <A NAME="bhsic1">&#160;</A>
<B>Using Inductive Counting to Simulate Nondeterministic
Computation</B>, G. Buntrock, L.&nbsp;Hemachandra,
and D. Siefkes, 
Information and Computation,
V.&nbsp;102, #1, pp.&nbsp;102-117, 1993.<LI> <A NAME="golhemkencompcompaddress">&#160;</A> 
<B>
Polynomial-Time Compression</B>,
J. Goldsmith, L.&nbsp;Hemachandra, and K. Kunen,
Computational Complexity,
V.&nbsp;2, #1, pp.&nbsp;18-39, 1992.<LI> <A NAME="allhemogiwatsicomp1">&#160;</A>
<B>Relating Equivalence and Reducibility to
Sparse Sets</B>, E. Allender,
L.&nbsp;Hemachandra, M. Ogiwara, and O. Watanabe, 
SIAM Journal on Computing,
V.&nbsp;21, #3, pp.&nbsp;521-539,
June 1992.<LI> <A NAME="allhemjacm1">&#160;</A> 
<B>Lower 
Bounds for the Low Hierarchy</B>,
E.&nbsp;Allender and L.&nbsp;Hemachandra, 
Journal of the ACM, V.&nbsp;39, #1, pp.&nbsp;234-250,
January 1992.<LI> <A NAME="hemrubtcs1">&#160;</A> 
<B>Separating Complexity
Classes with Tally Oracles</B>, L.&nbsp;Hemachandra and
R.&nbsp;Rubinstein,
Theoretical Computer Science, V.&nbsp;92, #2, pp.&nbsp;309-318,
January 1992.<LI> <A NAME="epphemtisyenmst1">&#160;</A> 
<B>Simultaneous Strong Separations of 
Probabilistic and Unambiguous Complexity Classes</B>, 
D.&nbsp;Eppstein, L.&nbsp;Hemachandra,
J.&nbsp;Tisdall, and B.&nbsp;Yener,
Mathematical Systems Theory, V.&nbsp;25, #1, pp.&nbsp;23-36, 1992.<LI> <A NAME="hemhoesicomp1">&#160;</A>
<B>On Sets With Efficient Implicit Membership Tests</B>, L.&nbsp;Hemachandra
and A.&nbsp;Hoene, 
SIAM Journal on Computing, V.&nbsp;20, #6, pp.&nbsp;1148-1156,
December 1991.<LI> <A NAME="hemjaiijfcspos">&#160;</A>
<B>On the Limitations of Locally Robust Positive 
Reductions</B>, L.&nbsp;Hemachandra and S.&nbsp;Jain, 
International Journal of Foundations of Computer Science,
V.&nbsp;2, #3, pp.&nbsp;237-255, September 1991.<LI>
<B>Near-Testable Sets</B>,
J. Goldsmith, L.&nbsp;Hemachandra, D. Joseph, and P. Young,
SIAM Journal on Computing, 
V.&nbsp;20, #3, pp.&nbsp;506-523, June 1991.<LI> <A NAME="hemwectcs1">&#160;</A>
<B>Kolmogorov Characterizations of Complexity Classes</B>, 
L.&nbsp;Hemachandra and G. Wechsung,
Theoretical Computer Science, V.&nbsp;83, #2,
pp.&nbsp;313-322,
June 1991.<LI> 
<B>A Note on Enumerative Counting</B>, 
J. Cai and L.&nbsp;Hemachandra,
Information Processing Letters, V.&nbsp;38, #4,
pp.&nbsp;215-219, May 1991.<LI> <A NAME="harhemtcs3">&#160;</A>
<B>One-Way Functions
                and the Non-Isomorphism of NP-Complete Sets</B>,
J. Hartmanis and L.&nbsp;Hemachandra,
Theoretical Computer Science, V.&nbsp;81, #1, pp.&nbsp;155-163, 
April 1991.<LI> <A NAME="hemhoesieyoutcs1">&#160;</A>
<B>On Sets Polynomially Enumerable By Iteration</B>,
L.&nbsp;Hemachandra, A.&nbsp;Hoene, D. Siefkes, and P. Young,
Theoretical Computer Science, V.&nbsp;80, #2,
pp.&nbsp;203-225, March 1991.<LI> <A NAME="beihemwecipl1">&#160;</A>
<B>Probabilistic
Polynomial Time is Closed Under
Parity Reductions</B>,
R.&nbsp;Beigel, L.&nbsp;Hemachandra, and G.&nbsp;Wechsung, 
Information Processing Letters, V.&nbsp;37, #2, 
pp.&nbsp;91-94, January 1991.<LI> <A NAME="hemrudjcss1">&#160;</A>
<B>On the Complexity of Ranking</B>, 
L. Hemachandra and S. Rudich,
Journal of Computer and System Sciences, 
V.&nbsp;41,
#2, pp.&nbsp;251-271, October 1990.<LI>  <A NAME="harhemtcs2">&#160;</A>
<B>Robust Machines Accept Easy Sets</B>,
J. Hartmanis and L.&nbsp;Hemachandra, 
Theoretical Computer Science, 
V. 74, #2, pp.&nbsp;217-226, 
August 1990.<LI><A NAME="caihemmst1">&#160;</A>
<B>On the Power of Parity Polynomial Time</B>,
J. Cai and L.&nbsp;Hemachandra,
Mathematical Systems Theory, 
V. 23, #2, pp.&nbsp;95-106, 1990.<LI> <A NAME="hemjcss1">&#160;</A>
<B>The Strong Exponential 
Hierarchy Collapses</B>, L. Hemachandra,
Journal of Computer and System Sciences, 
V. 39, #3, pp.&nbsp;299-322, December 1989.<LI> <A NAME="caiheminfcomp1">&#160;</A>
<B>Enumerative Counting is Hard</B>,
J. Cai and L. Hemachandra,
Information and Computation,
V. 92, #1, 
pp.&nbsp;34-44, July 1989.<LI> <A NAME="caigunharhemsewwagwecsicomp2">&#160;</A>
<B>The Boolean Hierarchy II: Applications,</B>
J. Cai, T. Gundermann, J. Hartmanis, L.&nbsp;Hemachandra, V. Sewelson, K. Wagner,
and G. Wechsung, 
SIAM Journal on Computing, V.&nbsp;18, #1, 
pp.&nbsp;95-111, February 1989.<LI> <A NAME="caigunharhemsewwagwecsicomp1">&#160;</A>
<B>The Boolean Hierarchy I: Structural Properties,</B>
J. Cai, T. Gundermann, J. Hartmanis, L.&nbsp;Hemachandra, V. Sewelson, K. Wagner,
and G. Wechsung, 
SIAM Journal on 
Computing, V. 17, #6, pp.&nbsp;1232-1252, December 1988.<LI> <A NAME="harhemipl1">&#160;</A>
<B>On Sparse Oracles Separating Feasible Complexity Classes</B>,
J. Hartmanis and L.&nbsp;Hemachandra, 
Information Processing Letters, V. 28, pp.&nbsp;291-295,
August 1988.<LI> <A NAME="harhemtcs1">&#160;</A>
<B>Complexity Classes Without Machines: On Complete Languages
                for UP</B>, J. Hartmanis and L.&nbsp;Hemachandra,
Theoretical Computer Science, V. 58, pp.&nbsp;129-142, 1988.<LI> <A NAME="gamhemshpweiieeeit1">&#160;</A>
<B>Using Simulated Annealing to Design Good Codes</B>, A. El Gamel, 
L. Hemachandra, I. Shperling, and V. Wei,
IEEE Transactions on Information Theory,
V. IT-33, #1, pp.&nbsp;116-123, January 1987.
<P>
</OL><BR> <HR>
<UL> 
<LI> <!WA6><A NAME="tex2html3" HREF="http://www.cs.rochester.edu/u/lane/node1.html#SECTION00010000000000000000">  About this document ... </A>
</UL>
<HR><!WA7><A NAME="tex2html1" HREF="http://www.cs.rochester.edu/u/lane/node1.html"><!WA8><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.cs.rochester.edu/u/jag/icons/next_motif.gif"></A> <!WA9><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.cs.rochester.edu/u/jag/icons/up_motif_gr.gif"> <!WA10><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.rochester.edu/u/jag/icons/previous_motif_gr.gif">   <BR>
<B> Next:</B> <!WA11><A NAME="tex2html2" HREF="http://www.cs.rochester.edu/u/lane/node1.html">  About this document </A>
<P><ADDRESS>
<I>Lane A. Hemaspaandra <BR>
Sun Nov 10 19:37:18 EST 1996</I>
</ADDRESS>
</BODY>
</HTML>
